#include <stdio.h>
int map[1001], q1[1001], len1, ans1[1001], q2[1001], len2, ans2[1001], ans=2147483647;
int lower_bound(int i, int* len, int* seq) {
	int l=1,r=*len;
	while(l<=r) {
		int m=(l+r)>>1;
		if(seq[m]<i)l=m+1;
		else r=m-1;
	}
	return l;
}
#define MIN(a,b) ((a)<(b)?(a):(b))
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)scanf("%d", &map[i]);
    for(int i = 1; i <= n; i ++)
    {
        if(map[i]>q1[len1])
            q1[++len1] = map[i];
        else
            q1[lower_bound(map[i],&len1,q1)] = map[i];
        if(map[n-i+1]>q2[len2])
            q2[++len2] = map[n-i+1];
        else
            q2[lower_bound(map[n-i+1],&len2,q2)] = map[n-i+1];
        ans1[i]=i-len1;
        ans2[i]=i-len2;
    }
    for(int i = 0; i <= n; i ++)
    {
        ans = MIN(ans, ans1[i]+ans2[n-i]);
        }
    printf("%d", ans);
    return 0;
}
